import random


class SudokuGenerator:
    def __init__(self):
        self.board = [[0 for _ in range(9)] for _ in range(9)]
        self.digits = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    def generate_board(self):
        """生成一个完整的、有效的数独棋盘"""
        self._solve_randomly()
        return self.board

    def get_puzzle(self, difficulty='medium'):
        """生成一个数独谜题，难度可以是 'easy', 'medium', 'hard'"""
        self.generate_board()
        difficulty_levels = {
            'easy': 30,  # 保留30个数字
            'medium': 25,  # 保留25个数字
            'hard': 20  # 保留20个数字
        }
        cells_to_remove = 81 - difficulty_levels.get(difficulty, 25)

        # 随机挖空格子
        positions = [(i, j) for i in range(9) for j in range(9)]
        random.shuffle(positions)

        for i, j in positions[:cells_to_remove]:
            self.board[i][j] = 0

        # 转换为字符格式 ('.' 表示空格)
        return [[str(num) if num != 0 else '.' for num in row] for row in self.board]

    def _solve_randomly(self, row=0, col=0):
        """使用回溯法随机填充数独棋盘"""
        if row == 9:
            return True

        next_row = row if col < 8 else row + 1
        next_col = (col + 1) % 9

        # 随机打乱数字顺序
        random_digits = self.digits.copy()
        random.shuffle(random_digits)

        for num in random_digits:
            if self._is_valid(row, col, num):
                self.board[row][col] = num
                if self._solve_randomly(next_row, next_col):
                    return True
                self.board[row][col] = 0

        return False

    def _is_valid(self, row, col, num):
        """检查在指定位置放置数字是否有效"""
        # 检查行和列
        for i in range(9):
            if self.board[row][i] == num or self.board[i][col] == num:
                return False

        # 检查3x3小方块
        start_row = (row // 3) * 3
        start_col = (col // 3) * 3
        for i in range(3):
            for j in range(3):
                if self.board[start_row + i][start_col + j] == num:
                    return False

        return True


def generate_random_sudoku(difficulty='medium'):
    """生成随机数独谜题，返回字符格式的二维列表"""
    generator = SudokuGenerator()
    return generator.get_puzzle(difficulty)